#ifndef _LIBMUNIX_HASHTABLE_H_
#define _LIBMUNIX_HASHTABLE_H_

/*
 * Some code (C) 2004 Sun Microsystems, Inc. All rights reserved.
 */

int (*HashFunction)(uint32_t, void *);
int (*HashCompare) (uint16_t, uint16_t);



template <class T> class HashTable;

template<class T>
class HashNode
{
	HashNode(T t) { item = t; key = 0; next = 0; }
	T			item;
	uint16_t	key;
	HashNode *	next;

friend class HashTable;
};

template<class T>
class HashTable
{
public:
	HashTable(uint8_t n, HashFunction hf, HashCompare hc);
	virtual ~HashTable();

	void	Add(T);
	void	Remove(uint16_t key);

protected:
	uint8_t			numBuckets;
	HashNode **		buckets;
	HashFunction	hashFunction;
	HashCompare		hashCompare;
};

class hash
{
public:


	static long genkey(const char* s, uint8_t len)
	{
		register long   x = 0;
		register uint8  n = 0;
		register uint8  c;

		while(n++ < len)
		{
			c = *s;
			if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
				x = ((x*0x63c63cd9L)+0x9c39c33dL + c);
			else if (c >= '0' && c <= '9')
				x = ((x*0x63c63cd9L)+0x9c39c33dL + (c - '0'+'z'+1));
			else break;
			++s;
		}
		return x;
	}
};

static inline int DefaultHash(uint32_t nbuckets, void * data)
{
	return (data % nbuckets);
}

static inline int DefaultCompare(uint16_t k1, uint16_t k2)
{
	return (k1 == k2);
}

static inline int HashString(int nbuckets, const char * str)
{
	const char * c;
	ulong_t g;
	int h = 0;

	for (c = str; *c; c++)
	{
		h = (h << 4) + *c;
		if ((g = (h & 0xf0000000)) != 0) {
			h ^= (g >> 24);
			h ^= g;
		}
	}
	return (h % nbuckets);
}

template<class T>
HashTable::HashTable(uint8_t n, HashFunction hf, HashCompare hc)
{
	numBuckets = n;
	hashFunction = hf;
	hashCompare = hc;
	buckets = new HashNode[sizeof(HashNode*)*n];
}

template<class T>
HashTable::~HashTable()
{
	// TODO delete each bucket's pointer


	delete [] buckets;
}

template<class T>
void
HashTable::Add(T item)
{
	uint8_t bucket = hashFunction(numBuckets,item);
	buckets[bucket] = new HashNode(T);
}

template<class T>
void
HashTable::Remove(uint16_t key)
{
	buckets[key-1].next = buckets[key+1];
	delete buckets[key];
}


#endif /* HASHTABLE_H_ */
